package com.maze;

import java.io.File;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Stack;


/**
 * A*算法---迷宫中寻找最短路径
 *
 * @author fh
 *
 */
public class Maze {
    private static int[][] map = null;
    private static List<Node> openList = new ArrayList<Node>();// 开启列表
    private static List<Node> closeList = new ArrayList<Node>();// 关闭列表

    int Max_row = 10;
    int Max_col = 10;

    Node startPoint = null;
    Node endPoint = null;

    // 构建迷宫
    public Maze() {
    }

    public Maze(File file, int maxRow, int maxCol) {
        this.map = ReadCsv.readCsv2Array(file);
        this.Max_row = maxRow;
        this.Max_col = maxCol;
        this.startPoint = new Maze().new Node(0, 0, null);
        this.endPoint = new Maze().new Node(Max_row - 1, Max_col - 1, null);
    }

    public static void main(String[] args) {
//        int Max_row = 10;
//        int Max_col = 10;
        // 1代表通路、0代表障碍-----矩阵的邻接表方式记录图
//        map = new int[][] {// 地图数组
//                { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
//                { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
//                { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
//                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
//                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
//                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
//                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
//                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
//                { 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 },
//                { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 } };
//        String strPath = System.getProperty("user.dir").concat("/csv/");
//        map = ReadCsv.readCsv2Array(new File(strPath + "map1.csv"));
//        Map<Position,CELL> cell = ReadCsv.readCsv(new File(strPath + "maze1.csv"));
//
//        Node startPoint = new Maze().new Node(0, 0, null);
//        Node endPoint = new Maze().new Node(Max_row - 1, Max_col - 1, null);
//
//        seachWay(map, startPoint, endPoint, Max_row, Max_col);
//        数组地图
//        for (int i = 0; i < Max_row; i++) {
//            for (int j = 0; j < Max_col; j++) {
//                System.out.print(map[i][j]+" ");
//            }
//            System.out.print("\n");
//        }

//         Cell 地图
    }

    /**
     * 搜寻最短路径
     *
     */
    public List<Position> seachWay() {
        final int CONST_HENG = 10;// 垂直方向或水平方向移动的路径评分
        final int CONST_XIE = 14;// 斜方向移动的路径评分
        Node curNode = startPoint;
        List<Position> list = new ArrayList<Position>();
        if (startPoint.x < 0 || startPoint.y > Max_col || endPoint.x < 0
                || endPoint.y > Max_col || map[startPoint.x][startPoint.y] == 0
                || map[endPoint.x][endPoint.y] == 0) {
            throw new IllegalArgumentException("坐标参数错误！！");
        }

        openList.add(startPoint);
        while (!openList.isEmpty() && !openList.contains(endPoint)) {
            curNode = minList(openList);
            if (curNode.x == endPoint.x && curNode.y == endPoint.y
                    || openList.contains(endPoint)) {
                System.out.println("找到最短路径");
                while(!(curNode.x==startPoint.x&&curNode.y==startPoint.y)){
                    System.out.print("("+curNode.x+","+curNode.y+") ");
                    Position position = new Position(curNode.x, curNode.y);
                    list.add(position);
                    map[curNode.x][curNode.y]=2;
                    if (curNode.parentNode!=null) {
                        curNode=curNode.parentNode;
                    }
                }
                System.out.print("("+startPoint.x+","+startPoint.y+")\n ");
                Position position = new Position(startPoint.x, startPoint.y);
                list.add(position);
                map[startPoint.x][startPoint.y]=2;
                return list;
            }
            // 上
            if (curNode.y - 1 >= 0) {
                checkPath(curNode.x, curNode.y - 1, curNode, endPoint,
                        CONST_HENG);
            }
            // 下
            if (curNode.y + 1 < Max_col) {
                checkPath(curNode.x, curNode.y + 1, curNode, endPoint,
                        CONST_HENG);
            }
            // 左
            if (curNode.x - 1 >= 0) {
                checkPath(curNode.x - 1, curNode.y, curNode, endPoint,
                        CONST_HENG);
            }
            // 右
            if (curNode.x + 1 < Max_row) {
                checkPath(curNode.x + 1, curNode.y, curNode, endPoint,
                        CONST_HENG);
            }
            // 左上
            if (curNode.x - 1 >= 0 && curNode.y - 1 >= 0) {
                checkPath(curNode.x - 1, curNode.y - 1, curNode, endPoint,
                        CONST_XIE);
            }
            // 左下
            if (curNode.x - 1 >= 0 && curNode.y + 1 < Max_col) {
                checkPath(curNode.x - 1, curNode.y + 1, curNode, endPoint,
                        CONST_XIE);
            }
            // 右上
            if (curNode.x + 1 < Max_row && curNode.y - 1 >= 0) {
                checkPath(curNode.x + 1, curNode.y - 1, curNode, endPoint,
                        CONST_XIE);
            }
            // 右下
            if (curNode.x + 1 < Max_row && curNode.y + 1 < Max_col) {
                checkPath(curNode.x + 1, curNode.y + 1, curNode, endPoint,
                        CONST_XIE);
            }
            openList.remove(curNode);
            closeList.add(curNode);
        }
         if (!openList.contains(endPoint)) {
             System.out.println("一条路径都未找到！！！");
         }
         return list;
    }

    // 核心算法---检测节点是否通路
    private static boolean checkPath(int x, int y, Node preNode, Node endPoint,
                                     int c) {
        Node node = new Maze().new Node(x, y, preNode);
        // 查找地图中是否能通过
        if (map[x][y] == 0) {
            closeList.add(node);
            return false;
        }
        // 查找关闭列表中是否存在
        if (isListContains(closeList, x, y) != -1) {// 存在
            return false;
        }
        // 查找开启列表中是否存在
        int index = -1;
        if ((index = isListContains(openList, x, y)) != -1) {// 存在
            // G值是否更小，即是否更新G，F值
            if ((preNode.g + c) < openList.get(index).g) {
                countG(node, endPoint, c);
                countF(node);
                openList.set(index, node);
            }
        } else {
            // 不存在，添加到开启列表中
            node.setParentNode(preNode);
            count(node, endPoint, c);
            openList.add(node);
        }
        return true;
    }

    // 计算G,H,F值
    private static void count(Node node, Node eNode, int cost) {
        countG(node, eNode, cost);
        countH(node, eNode);
        countF(node);
    }

    // 计算G值
    private static void countG(Node node, Node eNode, int cost) {
        if (node.getParentNode() == null) {
            node.setG(cost);
        } else {
            node.setG(node.getParentNode().getG() + cost);
        }
    }

    // 计算H值
    private static void countH(Node node, Node eNode) {
        node.setF((Math.abs(node.getX() - eNode.getX()) + Math.abs(node.getY()
                - eNode.getY())) * 10);
    }

    // 计算F值
    private static void countF(Node node) {
        node.setF(node.getG() + node.getH());
    }

    // 集合中是否包含某个元素(-1：没有找到，否则返回所在的索引)
    private static int isListContains(List<Node> list, int x, int y) {
        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            if (node.getX() == x && node.getY() == y) {
                return i;
            }
        }
        return -1;
    }

    // 找最小值
    private static Node minList(List<Node> list) {
        Iterator<Node> i = list.iterator();
        Node candidate = i.next();

        while (i.hasNext()) {
            Node next = i.next();
            if (next.compareTo(candidate) < 0)
                candidate = next;
        }
        return candidate;
    }

    // 节点类
    private class Node {
        private int x;// X坐标
        private int y;// Y坐标
        private Node parentNode;// 父类节点
        private int g;// 当前点到起点的移动耗费
        private int h;// 当前点到终点的移动耗费，即曼哈顿距离|x1-x2|+|y1-y2|(忽略障碍物)
        private int f;// f=g+h

        public Node(int x, int y, Node parentNode) {
            this.x = x;
            this.y = y;
            this.parentNode = parentNode;
        }

        public int compareTo(Node candidate) {
            return this.getF() - candidate.getF();
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public Node getParentNode() {
            return parentNode;
        }

        public void setParentNode(Node parentNode) {
            this.parentNode = parentNode;
        }

        public int getG() {
            return g;
        }

        public void setG(int g) {
            this.g = g;
        }

        public int getH() {
            return h;
        }

        public void setH(int h) {
            this.h = h;
        }

        public int getF() {
            return f;
        }

        public void setF(int f) {
            this.f = f;
        }

        public String toString() {
            return "(" + x + "," + y + "," + f + ")";
        }
    }

    // 节点比较类
    class NodeFComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.getF() - o2.getF();
        }

    }

}
